#include <bits/stdc++.h>

using namespace std;

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

void printf_list(ListNode *head)
{
    ListNode *cur = head;
    while (cur != nullptr)
    {
        printf("%d ", cur->val);
        cur = cur->next;
    }
    printf("\n");
}

class Solution
{
public:
    // ListNode *reverseList(ListNode *head)
    // {
    //     if (head == nullptr)
    //     {
    //         return nullptr;
    //     }
    //     ListNode *dummy_head = new ListNode(0);
    //     dummy_head->next = head;
    //     ListNode *cur = dummy_head;
    //     ListNode *node = cur->next;
    //     while (node != nullptr)
    //     {
    //         ListNode *nextnode = node->next;
    //         ListNode *curnode = node;
    //         node->next = cur;
    //         node = nextnode;
    //         cur = curnode;
    //     }
    //     head->next = nullptr;
    //     delete dummy_head;
    //     dummy_head = nullptr;
    //     return cur;
    // }

    // ListNode *reverseList(ListNode *head)
    // {
    //     ListNode *pre = nullptr;
    //     ListNode *cur = head;
    //     while (cur != nullptr)
    //     {
    //         ListNode *tmp = cur->next;
    //         cur->next = pre;
    //         pre = cur;
    //         cur = tmp;
    //     }
    //     return pre;
    // }

    // ListNode *recursion(ListNode *pre, ListNode *cur)
    // {
    //     if (cur == nullptr)
    //     {
    //         return pre;
    //     }
    //     ListNode *tmp = cur->next;
    //     cur->next = pre;
    //     pre = cur;
    //     return recursion(pre, tmp);
    // }

    // ListNode *reverseList(ListNode *head)
    // {
    //     ListNode *pre = nullptr;
    //     return recursion(pre, head);
    // }

    ListNode *reverseList(ListNode *head)
    {
        if (head == nullptr)
        {
            return head;
        }
        if (head->next == nullptr)
        {
            return head;
        }
        ListNode *last = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return last;
    }
};

int main()
{
    ListNode *head = new ListNode(1);
    ListNode *node1 = new ListNode(2);
    ListNode *node2 = new ListNode(3);
    ListNode *node3 = new ListNode(4);
    ListNode *node4 = new ListNode(5);

    head->next = node1;
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;

    printf_list(head);

    Solution sol;

    ListNode *reverse_head = sol.reverseList(head);

    printf_list(reverse_head);

    return 0;
}